1. Technical Field of the Invention
The present invention relates to the generation of Pseudo-Random Bit Sequences (PRBS).
2. Background of the Invention
The present invention discloses a method of generating a Pseudo-Random Bit Sequence (PRBS). The utility of such random numbers includes the creation of cryptography keys, the generation of bit stream ciphers and hash functions, and the testing of circuits and circuit simulations to detect and correct design errors.
A PRBS Generator is typically based on a Linear Feedback Shift Register (LFSR). An LFSR consists of a series of flip-flops connected by Exclusive-Or (XOR) gates, allowing for the output of one or more flip-flops to be input into a subsequent flip-flop. The PRBS Generator will cycle one bit location, or stage, to be output from the LFSR over each clock cycle or period, until each of bit locations 1 to n (where n=datapath width) is output and fed back into the first bit location. Because LFSRs vary in size (4-bits, 16-bits, 64-bits, etc), they will repeat themselves once each bit location or stage is fed back and input into the first bit location. FIG. 1 illustrates a prior art example, where a four-bit LFSR (3) receives input data (1) and cyclically shifts the data by outputting the information from the third bit location (6) and fourth bit location (7), XORing the data together, and creating a new state to be fed back into the first bit location (4). Therefore, in a four-bit LFSR, for each bit to be output from each bit location requires 4 clock periods, where one bit is output each cycle. The input bit is therefore a result of a linear function of the present state LFSR (the XORing of bits from the LFSR), with next state data shifting cyclically through the circuit through a feedback loop to generate a pseudo-random output (2). The LFSR generates a PRBS pattern, which may appear to be truly random but is actually pseudo random due to the deterministic nature of computer-based operations: each of the values produced by the LFSR are determined by the present and next states and because the LFSR is deterministic, the present state can be used to predict the next state.
A four-bit, PRBS Generating LFSR can be represented by the polynomial 1+x3+x4, where each clock cycle or period outputs one bit, and the four bit locations (or taps) of the LFSR are x1, x2, x3 and x4. In the first clock cycle, the latter two bit locations of the present state, x3 and x4, are XORed together and fed back into the first bit location, x1, so the new value (x3 XOR x4) is located in the first bit location and the x1 value is shifted into the second bit location (formerly x2). As illustrated in FIG. 2, as the circuit continues to XOR the last two bit locations and shift the new values back, the following feedbacks to the first bit location or stage occur:
Feedback [1]=x3 XOR x4
Feedback [2]=x2 XOR x3
Feedback [3]=x1 XOR x2
Feedback [4]=x1 XOR (x3 XOR x4)
After four full clock cycles, the value of the first bit location is (x1 XOR (x3 XOR x4)); the second bit location is (x1 XOR x2); the third bit location is (x2 XOR x3); and the fourth bit location is (x3 XOR x4). The LFSR then repeats itself and continues to shift data through the circuit to generate a PRBS pattern.
Several problems exist with this method of using LFSRs to generate PRBS patterns. First, there is a large amount of latency produced where the LFSR can only output one bit per clock cycle: to output 4 bits from a 4 bit LFSR requires 4 clock cycles; to output 16 bits from a 16 bit LFSR requires 16 clock cycles; etc. The speed of the output also depends on the number of XOR gates the data must travel through; the larger the size of the LFSR, the larger the size of the logic element required to accommodate it, and the larger the number of XOR gates needed.